public class Code2 {
    // 打家劫舍II
    // 这里使用了循环数组

    public int rob(int[] nums) {
        // 1、创建 dp 表
        // 2、初始化
        // 3、填表
        // 4、返回值

        // 首先先获取一下数组的长度
        int n = nums.length;
        // 针对这个问题，我们要简单分析一下，这里可以进行分类讨论
        // 1、上来直接偷取第一间房间此时，nums[0] 和 nums[n] 都不能再进去了,此时范围就是（0,2 ~ n-2）
        // 2、上来先不偷，从 nums[1] 的位置偷取，此时范围就是（1 ~ n-1）
        return Math.max(nums[0] + rob1(nums, 2, n-2), rob1(nums,1, n - 1));
    }

    public int rob1(int[] nums, int left, int right){
        if(left > right){
            return 0;
        }
        // 这里创建 dp 表我们可以创建和 nums 同样规模大小的数组，这样可以避免映射的问题
        int n = nums.length;
        // 这里需要创建出两个 dp 表，用来存放当前房间是否选择的两种情况
        // f[i] 表示的是偷到 i 位置时，偷取 nums[i]，此时的最大金额值
        // g[i] 表示的是偷到 i 位置时，不偷取 nums[i]，此时的最大金额
        int[] f = new int[n];
        int[] g = new int[n];

        f[left] = nums[left];
        // 这里的 i 是从当前 left 位置的下一位开始计算
        for(int i = left + 1; i <= right; i++){
            // 此时 f 就是不偷取 nums[i] 位置的最大值 + 当前 i 位置的值
            f[i] = g[i - 1] + nums[i];
            // 此时需要考虑 g[i - 1] 的位置有没有选择偷取，就需要与 f[i - 1] 比较
            g[i] = Math.max(g[i - 1],f[i - 1]);
        }
        // 此时返回的是两个表中的最后位置最大值
        return Math.max(f[right],g[right]);
    }
}
